package com.classicalAlgorithm.LFU;

import java.util.HashMap;
import java.util.LinkedHashSet;

public class LFU {

}

/*
*
*
LFUCache(int capacity) - 用数据结构的容量 capacity 初始化对象
int get(int key) - 如果键存在于缓存中，则获取键的值，否则返回 -1。
void put(int key, int value) - 如果键已存在，则变更其值；如果键不存在，请插入键值对。当缓存达到其容量时，则应该在插入新项之前，使最不经常使用的项无效。在此问题中，当存在平局（即两个或更多个键具有相同使用频率）时，应该去除 最久未使用 的键。
*
*
*
* */

// 「项的使用次数」就是自插入该项以来对其调用 get 和 put 函数的次数之和。
// 使用次数会在对应项被移除后置为 0 。
class LFUCache {
    // key到val的映射，后面称之为kv表
    HashMap<Integer, Integer> keyToVal;

    // key到freq的映射，后面称之为FK表
    HashMap<Integer, Integer> keyToFreq;

    // freq到key列表的映射，称之为FK表
    HashMap<Integer, LinkedHashSet<Integer>> freqTokeys;

    // 记录最小的频次
    int minFreq;

    // 记录LFU缓存的最大容量
    int cap;

    // LFUCache(int capacity) - 用数据结构的容量 capacity 初始化对象
    public LFUCache(int capacity) {
        keyToVal = new HashMap<>();
        keyToFreq = new HashMap<>();
        freqTokeys = new HashMap<>();

        this.cap = capacity;
        this.minFreq = 0;
    }

    // int get(int key) - 如果键存在于缓存中，则获取键的值，否则返回 -1。
    public int get(int key) {
        if (!keyToVal.containsKey(key)) {
            return -1;
        }

        // 增加对应key的访问频次
        increaseFreq(key);

        return keyToVal.get(key);
    }


    // void put(int key, int value) - 如果键已存在，则变更其值；
    // 如果键不存在，请插入键值对。
    // 当缓存达到其容量时，则应该在插入新项之前，使最不经常使用的项无效。
    // 在此问题中，当存在平局（即两个或更多个键具有相同使用频率）时，应该去除 最久未使用 的键。


    public void put(int key, int value) {
        if (this.cap <= 0)
            return;

        // 若key已经存在 修改对应的val即可
        if (keyToVal.containsKey(key)) {
            // 修改对应key的val
            keyToVal.put(key, value);

            // 增加key对应的使用频次
            increaseFreq(key);

            return;
        }


        // key不存在时，需要插入
        // 如果容量满的话，需要将freq最小的淘汰掉
        if (this.cap <= keyToVal.size()) {
            removeMinFreqKey();
        }

        // 插入key和value
        // 插入kv表
        keyToVal.put(key, value);

        // 插入kf表
        keyToFreq.put(key, 1);

        // 插入fk表
        freqTokeys.putIfAbsent(1, new LinkedHashSet<>());
        freqTokeys.get(1).add(key);

        // 插入新key后，最小的freq肯定是1
        this.minFreq = 1;
    }

    // 核心算法
    // 增加对应key的访问频次
    private void increaseFreq(int key) {
        int freq = keyToFreq.get(key);

        // 更新KF表
        keyToFreq.put(key, freq + 1);

        // 更新FK表
        // 将key从对应的freq->[key1.key2,...]中删除
        freqTokeys.get(freq).remove(key);

        // 将key加入到freq+1的对应的列表之中
        freqTokeys.putIfAbsent(freq + 1, new LinkedHashSet<>());
        freqTokeys.get(freq + 1).add(key);

        // 如果freq对应的key集合空了，则移除这个freq
        if (freqTokeys.get(freq).isEmpty()) {
            freqTokeys.remove(freq);
            // 如果这个freq恰好是minFreq，更新minFreq
            if (freq == this.minFreq) {
                this.minFreq++;
            }
        }
    }

    // 核心算法
    // 移除频率最小的那一个key
    private void removeMinFreqKey() {
        // freq最小的key列表
        LinkedHashSet<Integer> keyList = freqTokeys.get(this.minFreq);

        // 其中，最先插入的那个key就是该淘汰的key
        int deletedKey = keyList.iterator().next();

        // 更新freq->key FK表
        keyList.remove(deletedKey);

        // 如果最小freq的列表空了，就将这个freq从FK中删除
        if (keyList.isEmpty()) {
            freqTokeys.remove(this.minFreq);
            // 高频考点：需要在这里更新minFeq的值吗？
            // 因为只会在put时调用该方法，而每次put最后都会将minFreq赋值为1
        }

        // 更新KV表
        keyToVal.remove(deletedKey);

        // 更新KF表
        keyToFreq.remove(deletedKey);
    }


}



class Node {
    public int key;
    public int value;
    public int freq;
    public Node prev;
    public Node next;

    public Node() {
    }

    public Node(int key, int value) {
        this.key = key;
        this.value = value;
    }
}


class DoubleLinkedList {
    private final Node head;
    private final Node tail;
    public int size;

    public DoubleLinkedList() {
        this.head = new Node();
        this.tail = new Node();
        head.next = tail;
        tail.prev = head;
        size = 0;
    }

    public void remove(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
        size--;
    }

    public void addLast(Node node) {
        node.next = tail;
        node.prev = tail.prev;
        tail.prev = node;
        size++;
    }

    public void addFirst(Node node) {
        node.prev = head;
        node.next = head.next;
        head.next = node;
        size++;
    }

    public Node removeFirst() {
        if (head.next == tail) {
            return null;
        }
        Node first = head.next;
        first.next.prev = head;
        head.next = first.next;
        size--;
        return first;
    }

    public Node removeLast() {
        if (tail.prev == head) {
            return null;
        }
        Node last = tail.prev;
        last.prev.next = tail;
        tail.prev = last.prev;
        size--;
        return last;
    }
}

class LFUCache01 {
    // key -> node
    HashMap<Integer, Node> keyToNode;

    // 存储每个频次对应的双向链表  freq -> [ node1 - node 2 - node3]
    HashMap<Integer, DoubleLinkedList> freqToNodes;

    // 这里也可以直接用LinkedHashSet
    int size;
    int capacity;
    int minFreq;

    public LFUCache01(int capacity) {
        keyToNode = new HashMap<>(capacity);
        freqToNodes = new HashMap<>();
        this.capacity = capacity;
        this.minFreq = 0;
    }

    public int get(int key) {
        // 先看看是否有这个key
        if (!keyToNode.containsKey(key)) {
            return -1;
        }
        Node node = keyToNode.get(key);
        increaseKeyFreq(key);
        return node.value;
    }

    public void put(int key, int value) {
        if (this.capacity == 0) {
            return;
        }

        // 如果已经存在这个key
        if (keyToNode.containsKey(key)) {
            Node node = keyToNode.get(key);
            node.value = value;
            increaseKeyFreq(key);
            return;
        }

        // 不存在这个key 需要插入进去
        // 容量满了
        if (this.size >= this.capacity) {
            // 删除频次最小的key
            removeMinFreqKey();
            // 这里不用维护minFreq，因为下面会将minFreq置为1
        }

        // 插入新的key value
        // 更新keyToNode表
        Node newNode = new Node(key, value);
        keyToNode.put(key, newNode);

        // 更新freqToNodes表
        freqToNodes.putIfAbsent(1, new DoubleLinkedList());
        freqToNodes.get(1).addLast(newNode);

        this.size++;
        this.minFreq = 1;
    }

    private void increaseKeyFreq(int key) {
        Node node = keyToNode.get(key);
        int freq = node.freq;

        // 从原来的freq中删除
        DoubleLinkedList linkedList = freqToNodes.get(freq);
        linkedList.remove(node);

        // 如果删除后，freq链表中元素为空，则移除掉这个freq
        if (linkedList.size == 0) {
            freqToNodes.remove(freq);

            // 如果该频率正好为最低的频率
            if (this.minFreq == freq) {
                this.minFreq++;
            }
        }

        // 将该node加入到freq+1的双向链表中，从队列尾加入
        node.freq++;
        freqToNodes.putIfAbsent(freq + 1, new DoubleLinkedList());
        freqToNodes.get(freq + 1).addLast(node);
    }

    // 删除最小频率的key
    private void removeMinFreqKey() {
        DoubleLinkedList linkedList = freqToNodes.get(this.minFreq);

        // 删除队头  队头是插入最久的
        Node delNode = linkedList.removeFirst();

        // 更新 KN表
        keyToNode.remove(delNode.key);
        size--;
    }
}



class LFUCache02 {
    // key -> node
    HashMap<Integer, Node> keyToNode;

    // 存储每个频次对应的双向链表  freq -> [ node1 - node 2 - node3]
    HashMap<Integer, DoubleLinkedList> freqToNodes;

    //
    // HashMap<Integer, LinkedHashSet<Integer>> freqTokeys;


    // 这里也可以直接用LinkedHashSet

    int size;
    int capacity;
    int minFreq;

    public LFUCache02(int capacity) {
        keyToNode = new HashMap<>(capacity);
        freqToNodes = new HashMap<>();
        this.capacity = capacity;
    }

    public int get(int key) {
        Node node = keyToNode.get(key);
        if (node == null) {
            return -1;
        }
        increaseKeyFreq(key);
        return node.value;
    }

    public void put(int key, int value) {
        if (this.capacity == 0) {
            return;
        }

        // 如果已经存在这个key
        if (keyToNode.containsKey(key)) {
            Node node = keyToNode.get(key);
            node.value = value;
            increaseKeyFreq(key);
            return;
        }

        // 不存在这个key 需要插入进去
        // 容量满了
        if (this.size >= this.capacity) {
            // 删除频次最小的key
            removeMinFreqKey();

            // 这里不用维护minFreq，因为下面会将minFreq置为1
        }

        // 插入新的key value
        //  cacheAdd(key, value);
        Node newNode = new Node(key, value);
        keyToNode.put(key, newNode);

        freqToNodes.putIfAbsent(1, new DoubleLinkedList());
        freqToNodes.get(1).addLast(newNode);

        this.size++;
        this.minFreq = 1;
    }

    private void increaseKeyFreq(int key) {
        Node node = keyToNode.get(key);
        int freq = node.freq;

        // 从原来的freq中删除
        DoubleLinkedList linkedList = freqToNodes.get(freq);
        linkedList.remove(node);

        // 如果删除后，freq链表中元素为空，则移除掉这个freq
        if (linkedList.size == 0) {
            freqToNodes.remove(freq);

            // 如果该频率正好为最低的频率
            if (this.minFreq == freq) {
                this.minFreq++;
            }
        }

        // 将该node加入到freq+1的双向链表中，从队列尾加入
        node.freq++;
        freqToNodes.putIfAbsent(freq + 1, new DoubleLinkedList());
        freqToNodes.get(freq + 1).addLast(node);
    }

    // 删除最小频率的key
    private void removeMinFreqKey() {
        DoubleLinkedList linkedList = freqToNodes.get(this.minFreq);

        // 删除队头  队头是插入最久的
        Node delNode = linkedList.removeFirst();

        // 更新 KN表
        keyToNode.remove(delNode.key);
        size--;
    }
}
